Op deze pagina kunt u een gedetailleerde analyse krijgen van een woord of zin, geproduceerd met behulp van de beste kunstmatige intelligentietechnologie tot nu toe:
PL, ou L probabilístico, é a classe de linguagens reconhecíveis por uma máquina randômica de espaço logarítmico de tempo polinomial com probabilidade > 1/2 (chamado de erro ilimitado). De forma equivalente, como mostrado abaixo, PL é a classe de linguagens reconhecidas por máquinas randômizadas de tempo ilimitado e de espaço log com erro ilimitado.
Um exemplo de problema PL completo (sob redução logspace) é encontrar se o determinante de uma matriz (com coeficientes inteiros) é positivo. Dados uma matriz M e um número n, testar se |M| > n é também PL completo. Por outro lado, testar se o permanente de uma matriz é positiva é PP completo.
PLPL=PL no sentido de que para cada f em PL, PL é inalterada se for alargada para x→f(A,x) como uma subrotina, onde A é a string de entrada. PL contém NL e BPL , e está contida em NC2.